package cn.djb.day12;

import cn.djb.day2.ListNode;

class Solution_2 {

    public static void main(String[] args) {
        ListNode headA = new ListNode(-1);
        ListNode headB = new ListNode(-1);
        ListNode temA = headA;
        ListNode temB = headB;

        for (int i = 0; i < 20000000; i++) {
            temA = temA.next = new ListNode(i);
            temB = temB.next = new ListNode(i);
        }

        temA.next = temB;

        long tiem = System.currentTimeMillis();
        new Solution_2().getIntersectionNode2(headA, headB);
        System.out.println(System.currentTimeMillis() - tiem);

        tiem = System.currentTimeMillis();
        new Solution_2().getIntersectionNode(headA, headB);
        System.out.println(System.currentTimeMillis() - tiem);
    }

    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        while (A != B) {
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode tmpA = headA, tmpB = headB;
        int countA = 1, countB = 1;

        while (tmpA.next != null) {
            countA++;
            tmpA = tmpA.next;

        }
        while (tmpB.next != null) {
            countB++;
            tmpB = tmpB.next;
        }

        if (tmpA != tmpB) {
            return null;
        }

        int diff = Math.abs(countA - countB);

        if (countA < countB) {
            tmpA = headA;
            tmpB = headB;
        } else {
            tmpA = headB;
            tmpB = headA;
        }

        for (int i = 0; ; i++) {
            if (i < diff) {
                tmpB = tmpB.next;
            } else {
                if (tmpA == tmpB) {
                    return tmpA;
                }
                tmpB = tmpB.next;
                tmpA = tmpA.next;

            }
        }
    }
}